package middle;

import java.util.ArrayList;
import java.util.List;
import util.PrintUtils;

public class Solution_986 {

    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> list = new ArrayList<>();
        int second_index = 0;
        for (int i = 0; i < firstList.length; i++) {
            for (; second_index < secondList.length; second_index++) {
                if (secondList[second_index][1] > firstList[i][1]) {
                    merge(list, firstList, i, secondList, second_index);
                    break;
                }
                merge(list, firstList, i, secondList, second_index);
            }
        }
        return list.toArray(new int[][]{});
    }

    private void merge(List<int[]> list, int[][] firstList, int firstIndex, int[][] secondList, int secondIndex) {
        int left = Math.max(firstList[firstIndex][0], secondList[secondIndex][0]);
        int right = Math.min(firstList[firstIndex][1], secondList[secondIndex][1]);
        if (left <= right) {
            list.add(new int[]{left, right});
            return;
        }
    }

    public static void main(String[] args) {
        Solution_986 model = new Solution_986();
//        int[][] ints = model.intervalIntersection(new int[][]{{0, 2}, {5, 10}, {13, 23}, {24, 25}}, new int[][]{{1, 5}, {8, 12}, {15, 24}, {25, 26}});
//        int[][] ints = model.intervalIntersection(new int[][]{{0, 2}, {5, 10}}, new int[][]{});
        int[][] ints = model.intervalIntersection(new int[][]{{1, 7}}, new int[][]{{3, 10}});
        for (int[] array : ints) {
            PrintUtils.arrayInt(array);
        }
    }
}
